import java.util.*;

public class Solution5 {
    public static void main(String[] args) {
        int[] preorder = {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};
        Solution5 s = new Solution5();
        TreeNode treeNode = s.buildTree(preorder, inorder);


    }
    private int pre_index = 0;
    private int[] preorder;
    private Map<Integer,Integer> inorderMap = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //前序遍历，中左右
        //中序遍历，左中右
        this.preorder = preorder;
        for(int i=0;i<inorder.length;i++){
            inorderMap.put(inorder[i],i);
        }
        return _recurrent(0,inorder.length);
    }
    private TreeNode _recurrent(int left,int right){
        if(left == right){
            return null;
        }
        int preNums = preorder[pre_index];
        TreeNode root = new TreeNode(preNums);
        pre_index++;
        int inorederIndex = inorderMap.get(preNums);
        root.left = _recurrent(left,inorederIndex);
        root.right = _recurrent(inorederIndex+1,right);
        return root;
    }
}
